package LC;

/**
 * @ClassName LC204
 * @Description: TODO
 * @Author hl
 * @Date 2020/6/7
 * @Version V1.0
 **/
public class LC204 {
    public static void main(String[] args) {
        System.out.println(countPrimes(10));
    }

    public static int countPrimes(int n) {
        boolean []check=new boolean[n];
        for(int i=2;i<Math.sqrt(n);i++){
            if(!check[i]){
                for(int j=i*i;j<n;j=j+i){
                    check[j]=true;
                }
            }
        }
        int count=0;
        for(int i=2;i<n;i++){
            if(!check[i]){
                count++;
            }
        }
        return  count;
    }
}
